package 动态规划.背包问题;

/**
 * @ClassName _377组合总和IV
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2022/1/11 10:18
 * Version 1.0
 **/
public class _377组合总和IV {
/*    int count = 0;//回溯法，力扣超时
    int sum = 0;
    public int combinationSum4(int[] nums, int target) {
        backstack(nums,target,0);
        return count;
    }
    public int backstack(int[] nums, int target,int start){
        if(sum == target){
            count++;
            return 0; 
        }
        if(sum > target){
            return 0;
        }
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            backstack(nums,target,i + 1);
            sum -= nums[i];
        }
        return 0;
    }*/

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int j = 0; j <= target; j++){
            for(int i = 0; i < nums.length; i++){
                if(j - nums[i] >= 0){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}
